package com.datastructures2.unionFind;

/**
 * 加权quick-union算法 可用于解决大型问题
 * N个点M个连接最多访问数组cMlogN次，c为常数
 *
 * 综合了路径压缩 此算法已达最优效果
 * 此时成本数量级已非常接近1
 * @author MaoLin Wang
 * @date 2020/2/2911:57
 */
public class ComPathWeightedQuickUnionFind {
    private int[] id;
    private int[] weighted;
    private int count;

    public ComPathWeightedQuickUnionFind(int count) {
        this.count = count;
        weighted=new int[count];
        id = new int[count];
        for (int i = 0; i < count; i++) {
            weighted[i]=1;
            id[i]=i;
        }
    }

    /**
     * 加权quick-union算法，保证每次都将小树加到大树上
     * @param p
     * @param q
     */
    public void union(int p,int q){
        int i = find(p);
        int j = find(q);
        if (i==j){
            return;
        }else {
            if (weighted[i]<weighted[j]){
                id[i]=j;
                weighted[j] += weighted[i];
            }else {
                id[j]=i;
                weighted[i] += weighted[j];
            }
        }
        count--;
    }

    /**
     *  使用路径压缩，将路径上的所有节点都直接与根节点相连
     * @param p
     * @return
     */
    public int find(int p) {
        int root=p;
        while (root!=id[root]){
            root=id[root];
        }
        while (id[p]!=root){
            int temp=p;
            id[temp]=root;
            p=id[p];
        }
        return root;
    }
    public boolean connected(int p , int q){
        return find(p)==find(q);
    }
    public int count(){
        return count;
    }

    public static void main(String[] args) {
        ComPathWeightedQuickUnionFind unionFind = new ComPathWeightedQuickUnionFind(10);
        unionFind.union(4,3);
        unionFind.union(3,8);
        unionFind.union(6,5);
        unionFind.union(9,4);
        unionFind.union(2,1);
        unionFind.union(8,9);
        unionFind.union(5,0);
        unionFind.union(7,2);
        unionFind.union(6,1);
        unionFind.union(1,0);
        unionFind.union(6,7);
        int[] id = unionFind.id;
        for (int i = 0; i < id.length; i++) {
            System.out.println("id["+i+"]:"+id[i]);
        }
    }
}
